\documentclass{beamer}
\mode<presentation>
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage{amsmath, amssymb}
\usepackage[portugues]{algorithm2e}

% Beamer template settings
\usetheme{Copenhagen}
\usecolortheme{crane}
\setbeamertemplate{navigation symbols}{}

\title[Dynamic Content Distribution for Mobile Enterprise Network]
{Dynamic Content Distribution for Mobile Enterprise Network}
\author{Igor Giusti da Silva \and Fábio Gomes dos Santos}
\institute{UFF - IC - Instituto de Computação}
\date{\today}
\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Descrição do problema}

\begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
\end{frame}

\begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
\end{frame}

\subsection{Motivação}

\begin{frame}
  \frametitle{Motivação}
  \begin{itemize}
    \itemsep=0.3cm
    \item Distribuição de conteúdos corporativos
    \item Variação da demanda por um conteúdo
    \begin{itemize}
      \item Mobilidade dos usuários
      \item Popularidade dos conteúdos
    \end{itemize}
    \item Gerência dos conteúdos considera a variação de demanda
  \end{itemize}
\end{frame}

\subsection{Content Distribution Networks e Mobilidade}

\begin{frame}
  \frametitle{Content Distribution Network}

  \begin{columns}

    \begin{column}{6cm}
      \begin{itemize}
        \itemsep=0.3cm
        \item Distribui conteúdo entre servidores visando a diminuir o tráfego no backbone da rede
        \item Variação na demanda implicada pela variação da popularidade dos conteúdos
        \item Número de usuários em cada servidor tem pouca variação
        \item Período de reavaliação de configuração longos
      \end{itemize}
    \end{column}

    \begin{column}{6cm}
      \begin{figure}
        \includegraphics[scale=0.26]{../implementation/images/wired_cdn.png}
      \end{figure}
    \end{column}

  \end{columns}

\end{frame}

\begin{frame}
  \frametitle{CDN Móvel}

  \begin{columns}

    \begin{column}{6cm}
      \begin{itemize}
        \itemsep=0.3cm
        \item Alteração na demanda causada por:
        \begin{itemize}
          \item Mobilidade dos usuários
          \item Variação da popularidade dos conteúdos
        \end{itemize}
        \item O número de usuários em cada servidor varia
        \item Alta frequência de reconfiguração
      \end{itemize}
    \end{column}

    \begin{column}{6cm}
      \begin{figure}
        \includegraphics[scale=0.25]{../implementation/images/mobility.png}
      \end{figure}
    \end{column}

  \end{columns}

\end{frame}

\begin{frame}
  \frametitle{Serviço indireto}
 \begin{columns}

  \begin{column}{6 cm}
    \begin{enumerate}
      \itemsep=0.3cm
      \item Cliente faz requisição F.
      \item Conteúdo da requisição F não encontrado. Encaminha requisição.
      \item Servidor local recebe resposta de F. Encaminha resposta para cliente.
      \item Cliente recebe resposta de F.
    \end{enumerate}
  \end{column}

  \begin{column}{6 cm}
   \begin{figure}
      \includegraphics[scale=0.26]{../implementation/images/indirect_service.png}
   \end{figure}
  \end{column}

 \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Replicação}

  \begin{columns}

  \begin{column}{6 cm}
    \begin{enumerate}
      \itemsep=0.3cm
      \item Servidor decide replicar conteúdo R e requere uma cópia de R.
      \item Servidor mais próximo recebe a requisição e responde com a cópia de R.
      \item O servidor que fez a requisição recebe resposta de R.
    \end{enumerate}
  \end{column}

  \begin{column}{6 cm}
   \begin{figure}
      \includegraphics[scale=0.30]{../implementation/images/replication.png}
   \end{figure}
  \end{column}

\end{columns}

\end{frame}

\section{Algoritmo heurístico online}

\begin{frame}
  \frametitle{Principal problema}

  Todos os servidores devem saber em quais outros servidores cada conteúdo está presente.

  Para solução em um servidor $S$:
  \begin{itemize}
    \itemsep=0.3cm
    \item Armazenar as operações que $S$ faz em uma lista
    \item Fazer o \emph{broadcast} dessas operações
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Estruturas de dados - \emph{Vetor de lista de servidores}}

  \begin{figure}[h]
    \includegraphics[scale=0.5]{images/servers_for_content.png}
  \end{figure}

\end{frame}

\begin{frame}
  \frametitle{Estrutura de dados - \emph{Lista de operações}}

  \begin{figure}[h]
    \includegraphics[scale=0.5]{images/operation_list.png}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Estrutura de dados - Populando a lista de operações}

  A lista de operações é populada ao longo da previsão de demanda enquanto as decisões sobre os conteúdos são tomadas.

  \begin{algorithm}[H]

    \scriptsize
    \SetLine

    \For{$\forall$ conteúdo $c \in C$}{
      $\vdots$\\
      \uIf{não possuo o conteúdo $c$ e $bi^{c} > (br^{c} + bm^{c})$}{
        \emph{\textbf{Insiro na minha lista de operações o \emph{pull} de $c$}}\\
      }
      \ElseIf{possuo o conteúdo $c$ e não sou o servidor origem de $c$ e $bi^{c} > bm^{c}$}{
        \emph{\textbf{Insiro na minha lista de operações a \emph{remoção} de $c$}}\\
      }
    }

    \While{$load_{i} > HW$}{
        Fazer \emph{push} da réplica do conteúdo $c$ para $j \in S$ tal que $\max(d^{ic}_{j})$\\
        \emph{\textbf{Insiro na minha lista de operações o \emph{push} de $c$ para $j$}}
        $load_{i} \leftarrow load_{i} - d^{ic}_{j}$\\
    }

  \end{algorithm}

\end{frame}

\begin{frame}
  \frametitle{Estrutura de dados - \emph{Sincronizando os vetores de listas de servidores}}

  A lista de operações fornece as informações necessárias para atualizar os vetores de listas de servidores.

  Cada servidor deve enviar as operações que vai efetuar para os demais servidores. O envio das operações deve ser feito respeitando-se duas restrições:

  \begin{itemize}
    \itemsep=0.3cm
    \item A lista de operações de um servidor tem tamanho variável
    \item Todos os servidores devem enviar suas operações e receber as operações dos demais servidores
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Restrição - Lista de operações com tamanho variável}

  Para atender essa restrição, antes de fazer o \emph{broadcast} das operações, envia-se a quantidade de operações que serão enviadas. Desse modo, os servidores a receber as operações sabem o número de pacotes broadcast que esperam.

  \begin{figure}[h]
    \includegraphics[scale=0.5]{images/broadcast_data.png}
  \end{figure}
  
\end{frame}

\begin{frame}
  \frametitle{Restrição - Servidores devem enviar e receber}

  Para atender essa restrição, basta os servidores enviares em um sistema de turno no qual um servidor apenas envia enquanto os demais recebem o \emph{broadcast}. Se existirem $n$ servidores, então haverá $n$ turnos.

  \begin{figure}[h]
    \includegraphics[scale=0.5]{images/broadcast_turn.png}
  \end{figure}
  
\end{frame}

\begin{frame}
  \frametitle{Pseudo-código do \emph{broadcast} de operações}

  \begin{algorithm}[H]

    \scriptsize
    \SetLine

    \For{$sender \leftarrow 0$ \KwTo $nSERVERS$}{
      MPI\_Bcast($\cdots, number\_of\_operations, sender, \cdots$)\\
      \For{$counter \leftarrow 0$ \KwTo $number\_of\_operations$}{
        MPI\_Bcast($\cdots, operation, sender, \cdots$)\\
        Atualiza o \emph{VLS} de acordo com \emph{operation}
      }
    }

  \end{algorithm}

\end{frame}

\section{Imitando o simulador}

\begin{frame}
  \frametitle{Estrutura utilizada}
  Na simulação dividimos os 500.000 usuários nos grupos A,B,C,D com 5\%, 60\%, 30\% e 5\% respectivamente.
  \begin{itemize}
    \itemsep=0.3cm
    \item Para representar os grupos usamos um vetor de tamanho 4, onde cada elemento aponta um vetor de usuários.
    \item O vetor de usuários tem tamanho dependente da porcentagem de usuários destinada a um determinado grupo.
    \item Cada elemento do vetor de usuários possui um lista de conexões, onde são armazenados informações de timestamp, duração da chamada, conteúdo requisitado e servidor utilzado.
    \item Ao final da geração das informações de requisição, estas serão armazenadas em arquivos texto.
  \end{itemize}
\end{frame}


\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  A seguir analizaremos cada informação referente a conexão feita por um usuário:
\end{frame}

\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  \emph{Timestamp}: Marca o tempo entre chamadas feitas pelo usuário. Essa informação segue uma distribuição de Poisson e tem médias de 14, 7, 18, 18 para os grupos A, B,C, D respectivamente.\\[0.5cm]

  \begin{algorithm}[H]
    \SetLine
    \scriptsize 
    $poisson(\lambda)$\\
    \Begin {
        $u \leftarrow random$\\
        $stop \leftarrow e^{- \lambda}$\\
        $k \leftarrow 1$\\
        \Repeat{$u \leqslant stop$}{
            $u \leftarrow u \times random)$\\
            $k \leftarrow k + 1$;
        }
    
        \Return{$k - 1$}
    }
  \end{algorithm}
\end{frame}


\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  \emph{Duração}: Informa quanto tempo o usuário ficou conectado ao servidor. De forma indireta informa quantas requisições foram feitas nesse período, já que sabemos que a taxa de requisições de um usuário é 1 requisição/segundo. Essa informação segue uma distribuição exponencial com média de 60 segundos.\\[0.5cm]

  \begin{algorithm}[H]  
    \scriptsize	
    \SetLine
    $exponential(\lambda)$\\
    \Begin{
      $u \leftarrow random$\\
      \Return{$- \lambda \cdot \log_{e}u$}
    }
  \end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  \emph{Conteúdo requisitado}: Informa qual conteúdo foi requisitado pelo usuário. Essa informação segue uma distribuição zipf-like com parâmetro $\alpha = 0.84$.\\[0.5cm]

  \begin{algorithm}[H]
    \scriptsize	
    \SetLine
    $zipf(\alpha)$\\
    \Begin{
      \For{$content \leftarrow 1$ \KwTo $nCONTENTS$}{
        $ruler[content] \leftarrow 1 \div content^{\alpha}$\\
      }
      
      $normalize(ruler)$\\

      $content \leftarrow 1$\\
      $u \leftarrow random$\\
      \While{$u \geqslant 0$}{
        $u \leftarrow u - ruler[content]$
        $content \leftarrow content + 1$
      }
      \Return{$content$}
    }
  \end{algorithm}

\end{frame}


\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  \emph{Servidor utilizado}: Informa a qual servidor o usuário se conectou. Em nossa simulação usamos duas abordagens:

  \begin{itemize}
    \itemsep=0.3cm
    \item Com mobilidade: Utilizamos uma função que gera número de servidores aleatórios com limites diferentes para cada grupo.	 
    \item Sem mobilidade: Nessa abordagem simplesmente distribuimos os usuários de cada grupo entre os 16 servidores usados na simulação.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Cálculo dos valores de cada conexão}
  \emph{Função de mobilidade - Imagem:}
  \begin{figure}
      \includegraphics[scale=0.30]{../implementation/images/city_base.png}
  \end{figure}
\end{frame}


\begin{frame}
  \frametitle{Função de mobilidade}
	
  \begin{algorithm}[H]
    \scriptsize
    $geraServidorAleatorio(group, server)$//
	$begin \leftarrow 0$\\
        $end \leftarrow 0$\\

	    \Switch{$group$}{

	        \uCase{$0$}{
		        $begin \leftarrow 0$\\
		        $end \leftarrow nSERVERS - 1$\\
            }

	        \uCase{$1$}{
		        \If{$server < 0$}{
			        $begin \leftarrow 0$\\
			        $end \leftarrow nSERVERS - 1$\\
		        }{
			        $begin \leftarrow server$\\
			        $end \leftarrow server$\\
		        }
            }
            }		
  \end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Função de mobilidade (Continuação)}
  \begin{algorithm}[H]  
  \scriptsize
	\Switch{$group$}{
	        \uCase{$2$}{
		        \If{$server < 0$}{
			        $begin \leftarrow 0$\\
			        $end \leftarrow nSERVERS - 1$\\
		        }{
			        $begin \leftarrow server - 2$\\
			        \If{$begin < 0$}{$begin \leftarrow nSERVERS - 1$}
			        $end \leftarrow (server + 2) \mod nSERVERS$\\
		        }
            }

	        \uCase{$3$}{
                $iServer \leftarrow random(0, nSERVERS - 1)$\\
                \If{$(iServer \div 2) \neq 0$}{$iServer \leftarrow iServer + 1$}
	        }

		    \Return{$iServer$}
	    }

	    \Return{$random(begin, end)$}
  \end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Dificuldades encontradas}
  \begin{itemize}
    \itemsep=0.3cm
    \item Depuração no MPI
    \item Tamanho do artigo e referências
    \item Informações pouco claras
  \end{itemize}
\end{frame}


\end{document}
